void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin == end)
        return;
    int mid = (begin + end) / 2;
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid+1, end, tmp);
    
    
    int begin1 = begin, end1 = mid;
    int begin2 = mid+1, end2 = end;
    int i = begin;
    while (begin1 <= end1 && begin2 <=end2)
    {
        if (a[begin1] < a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }
    while(begin1<=end1)
        tmp[i++] = a[begin1++];
    while(begin2<=end2)
        tmp[i++] = a[begin2++];
    memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(a,0, n-1, tmp);
    free(tmp);
}

void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    int gap = 1;
    while (gap < n)
    {
        int j = 0;
        for (int i = 0; i < n; i+=2*gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            if (end1 >= n || begin2 >= n)
                break;
            if (end2 >= n)
                end2 = n - 1;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                    tmp[j++] = a[begin1++];
                else
                    tmp[j++] = a[begin2++];
            }
            while (begin1 <= end1)
                tmp[j++] = a[begin1++];
            while (begin2 <= end2)
                tmp[j++] = a[begin2++];
            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
        }
        gap *= 2;
    }
}